package 动态规划.dp声明正序And倒序.射箭比赛这道题的思维发散;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/25 17:24
 */
public class 射箭比赛dp加上路径记录解法 {



    /*
     还有灵神的 二进制的解法!
     */









    /*
     这个 是 dp 倒推!
     注意这个 可是 没有 创建 path 数组进行 路径记录:
     ==
     这两种实现方式,都要掌握 !
     */
    public int[] maximumBobPoints(int n, int[] as) {
        int m = as.length;
        //用i支箭，在j个标靶中，所能获得的最大的分数
        int[][] f = new int[n + 1][m + 1];
        //记录最大的得分
        int maxVal = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //不选择标靶j
                f[i][j] = f[i][j - 1];
                //选择标靶j
                if (i > as[j - 1])
                    f[i][j] = Math.max(f[i - as[j - 1] - 1][j - 1] + (j - 1), f[i][j]);

                maxVal = Math.max(maxVal, f[i][j]);
            }
        }
        int[] ans = new int[m];
        //倒推得出ans的值
        while (maxVal > 0 && n > 0) {
            for (int i = 1; i <= 12; i++) {
                if (f[n][i] == maxVal) {
                    ans[i - 1] = as[i - 1] + 1;
                    maxVal -= (i - 1);
                    n -= (as[i - 1] + 1);
                    break;
                }
            }
        }
        //把剩余的箭，全部加到ans[0]
        ans[0] += n;
        return ans;
    }




    /*
    === 路径还原01背包问题

     对这个 path[][] 进行一个解释, 如果 path[index][rest] = 0, 代表 dp[index][rest] 是 从 dp[index + 1][rest] 这条路过来的
     如果 path[index][rest] = 1 , 说明 dp[index][rest] 是从 dp[index + 1][rest - nums[index] - 1] 这条路过来,
     就是这样的 一个路径记录 !
     注意 dp[index + 1][rest] == dp[index + 1][rest - nums[index] - 1]  这种可能是存在的
     这种其实 是一种正常的现象!
     */
    public int []solution(int numArrows,int[] arrows){
        int len =  arrows.length,ans[] = new int[len],dp[][] =  new int[len + 1][numArrows + 1];
        int path[][] = new int[len + 1][numArrows + 1];
        for(int index = len - 1; index >= 0;index--){
            for(int rest = 1;rest <= numArrows;rest++ ){
                int ans1 = 0, ans2 = 0;
                ans1 = dp[index + 1][rest];
                if(rest - arrows[index] >= 1){
                    ans2 = Math.max(dp[index][rest],dp[index +1][rest - arrows[index] - 1] + index);
                }
                path[index][rest] = ans1 >= ans2 ? 0 : 1; // ans1 == ans2 随便选一个都可以!
                dp[index][rest] = Math.max(ans1,ans2);
            }
        }
        for(int i =1;i < len;i++){
//            if(path[i][numArrows] == 0 ){
//                ans[i] = 0; // 本来初始化 时就是 0, 这个其实没必要写了
//            }
//            else{
//                numArrows -= ans[i] = arrows[i] + 1;
//            }
            // 直接 这样写 就行了!
            if(path[i][numArrows] == 1){
                numArrows -= ans[i] = arrows[i] + 1;
            }

        }
        // 需要 把剩余的箭 放在 0 号位置上, 不这样写, 会与结果 不符合! 卧槽!
        ans[0] = numArrows;
//        System.out.println(dp[0][numArrows]);
        return ans;
    }


    @Test
    public void test(){
//        int arrows = 100000;
//        int arr[] = {0,0,0,0,0,0,0,0,0,0,0,100000};
        int arrows = 9;
        int arr[] = {1,1,0,1,0,0,2,1,0,1,2,0};
        int[] solution = solution(arrows, arr);
        System.out.println(Arrays.toString(solution));
    }


/*
 目前 最快的一个代码! 2ms
  直接回溯, 这他妈 是最快的!
  因为 满足的结果 过程 可能会多条 路径, 而回溯 只要找到一条路径 就直接返回, 根本就不会去计算全部的 结果! (应该是吧 ! 我不太确定)
 */
    class Solution {
        int max = 0;
        int[] ans = new int[12];
        public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
            dfs(aliceArrows,0,numArrows,0,new int[12]);
            return ans;
        }

        void dfs(int[] nums, int idx, int res, int point,int[] cur){
            if(idx == 11){
                if(point>max){
                    max = point;
                    ans = Arrays.copyOf(cur,cur.length);
                    if(res > 0){
                        ans[0] = res;
                    }
                }
                return;
            }
            if(res > nums[idx+1]){
                cur[idx+1] = nums[idx+1]+1;
                dfs(nums,idx+1,res-nums[idx+1]-1,point +idx+1,cur);
            }
            cur[idx+1] = 0;
            dfs(nums,idx+1,res,point,cur);
        }
    }


}
